1. Field of the Invention
The present invention relates to generally to calculating a discrete Fourier transform for signal processing, and, in particular, to an apparatus for calculating an N-point Discrete Fourier Transform.
2. Description of the Related Art
The Fourier transform is a mathematical formula for converting a signal from a time-domain representation to a frequency-domain representation. The discrete Fourier transform (“DFT”) may be viewed as a special case of the continuous form of the Fourier transform. The DFT determines a set of spectrum amplitudes from a time-varying signal defined by a periodic sequence of samples taken at discrete time intervals. Techniques developed for more rapid computation of the discrete Fourier transform have become known as the fast Fourier transform (“FFT”), first described in a paper by J. W. Cooley and J. W. Tukey, entitled “An Algorithm for the Machine Calculation of Complex Fourier Series,” Mathematics of Computation (1965), Vol. 19, No. 90, pp. 297-301, which is incorporated herein by reference in its entirety.
The FFT is an algorithm that is based on the fact that a discrete Fourier transformation can be generated by combining Fourier transformations of subsets of the input data. In general, the input data is divided into subsets of N data points on which an N-point discrete Fourier transform are performed. Two-point or four-point transforms are popular because the multiplications in two- or four-point Fourier transformations are all operations in which one of the factors is plus or minus unity or plus or minus the square root of minis one, however, other numbers of points may be used.
In a circuit for implementing a fast Fourier transformation, the hardware circuit for performing the N-point Fourier transformation is used repeatedly and is referred to as a butterfly circuit. The choice of what value of N to use depends on a number of factors, including the speed required and the number of sample points in each transformation. However, a four-point circuit can transform only input data whose number of samples is a multiple of 4. Thus, it may be desirable in some applications to use multiple circuits to support transforming data whose number of samples is not a multiple of 4.
An increasingly common technique for computing the fast Fourier transform is to employ a microprocessor programmed to perform the function. However, because of the generalized nature of microprocessor architecture, the relatively slow speed of computation is a significant limiting factor for many applications. Therefore, in view of the foregoing, it will be apparent that there has been a need for a fast Fourier transform circuit having that computes Fourier transform coefficients in parallel to achieve higher speed, allows for N to be selectable in computing an N-point discrete Fourier transform, and utilizes minimal physical space.